The present invention relates to navigation satellite receivers, and more particularly to methods and systems for aiding the initializing of navigation satellite receivers with limited prior knowledge of time and location.
Global positioning system (GPS) receivers use signals received from several earth-orbiting satellites to determine user position and velocity, and other navigational data. A navigation receiver that has just been turned on does not yet know where it is, how much its crystal oscillator is in error, nor what time it is. All these are needed to find and lock onto the satellite transmissions, and so a search must be made of all the possibilities.
Because the receiver and satellite clocks are not perfectly synchronized, such clock offset acts as an error on the distance to the satellite. The apparent distance is called the xe2x80x9cpseudorangexe2x80x9d (PR). The clock error can be computed by assuming all the pseudoranges to the different satellites will have the same clock offset in one measurement epoch. So four satellites are needed for a position fix, three for latitude, longitude and height or (X, Y and Z), and one for the clock offset.
Two different-length modulating codes are transmitted on two microwave carriers. The carrier wavelengths are nineteen and twenty-four centimeters. The precision (P) code is available only to authorized (military) users and does not have any ambiguity because its length is about 181,440,000,000 km, the distance traveled by light in one week. The coarse acquisition (C/A) code is much shorter and repeats every 300 km of radio wave propagation distance, so observations outside a range of 0-300 km can be ambiguous. Since the distance to a satellite is typically 20,000 km, which 300 km segment the receiver is in needs to be determined. This is called an integer ambiguity.
The Z-count is a 29-bit binary number that represents a fundamental GPS time unit. The ten most significant bits carry the GPS week number, and the nineteen least significant bits give the time of week (TOW) count in units of 1.5 seconds. A much finer gauge of the system time is available once the receiver locks onto a few satellites. Prior art devices have depended on determining the z-count during initialization.
Before GPS carrier phase observables can be used for positioning, the integer ambiguities must be resolved. The phase measurement is translated into a distance measurement. Conventional estimation techniques cannot solve the receiver coordinates, the clock offset and the integer ambiguities in one epoch of data, for all the satellites observed. Collecting a few epochs of data doesn""t help much. Although there are enough equations, the problem is insoluble, since the satellite""s geometry with respect to the receiver is not usually favorable enough. The integer ambiguity values can only be determined after a significant change in the geometry, unless an on-the-fly (OTF) technique is being used.
The two basic types of GPS positioning systems are real-time navigation and high-precision carrier phase positioning. Real-time navigation systems collect a minimum of four pseudorange (PR) measurements to four satellites. The PR measurements are used to solve for the three-dimensional coordinates of the receiver and the clock offset between the receiver oscillator and GPS system time. Differential GPS (DGPS) also collects the pseudorange observables, and further obtains real-time corrections for the errors inherent in the measurements.
Precise carrier-phase observations can be used to compute locations to within a few centimeters. Phase measurements of the short, different wavelengths of the two carriers (19-cm and 24-cm for L1 and L2 respectively), are used to resolve such. The whole number of complete wavelengths between the satellite and receiver, e.g., integer ambiguities, must first be determined. Post processing (static) or Real-Time (RTK) methods are used in the prior art that use linear combinations of the two frequencies and differencing techniques. The pseudorange can be combined with the phase data to reduce the noise error for much higher positioning accuracy.
During initialization, a navigation satellite receiver will search to find signal power from the available satellites. Which satellites are available depends on the respective satellites"" ephemeris, the user""s position on earth, and the time. A little bit of prior knowledge of any or all of these can be used to abbreviate the time, space, and frequency spectrums that must be searched. The navigation satellite receiver will then be able to produce its first position and velocity solution much quicker.
Mobile GPS receivers can be aided in their initialization by a remote server that can provide time, position, and/or frequency information. Such a prior art scheme is described by Samir Soliman, et al., in U.S. Pat. No. 6,081,229, issued Jun. 27, 2000, and is incorporated herein by reference.
Gilbert Strang, a professor of mathematics at MIT, wrote an article about integer ambiguities in the Society for Industrial and Applied Mathematics (SIAM) News, Volume 30, Number 5, June 1997. He says the receiver must know the count of the number of radio wavelengths between the satellites and the receiver. Such count is an integer number of phase changes plus a fraction of a phase. The integer part is initially unknown and is ambiguous. Its resolution has to be right, because one missing wavelength means an error of 19 cm or 24 cm, depending on whether the L1 or L2 carrier is being measured.
Once the integer is known, it is important to keep track of it. A loss-of-lock caused by losing signal can result in cycle slips. The fractional part is obvious, but the whole number of cycles is hard to discover and takes time. In GPS, there might be dozens of integer ambiguities to determine simultaneously, and is a problem in integer least squares. This is identical to the nearest lattice vector problem in computational combinatorics, e.g., minimize (xxe2x88x92x0)TA(xxe2x88x92x0) for x in Zn. The minimum over Rn is clearly zero, at x=x0. The lattice point x, the ambiguity vector, is closest to x0 in the metric of A. Such minimization over Zn is such a difficult problem for large random matrices A, that its solution has been used by cryptographers to encode messages.
In GPS, the weighting matrix A sometimes involves distances between receivers, and the problem is hardest for a global network. The minimization is easy when A is diagonal, because the variables are uncoupled. Each component of x will be the nearest integer to the corresponding component of x0. But an ill-conditioned A severely stretches the lattice. A direct search for the best x becomes horrible. The natural idea is to precondition A by diagonalizing as nearly as possible, always keeping the change of basis matrices Z and Zxe2x88x921 integral. Then yT(ZTAZ)y will be more nearly uncoupled than xTAx, and y=Zxe2x88x921x will be integral exactly when x is.
It is therefore an object of the present invention to provide a method and system for navigation satellite reception and receiver initialization that can proceed without an initial Z-count.
It is another object of the present invention to provide a method and system for shortening the time needed for initialization of navigation devices.
It is a further object of the present invention to provide a satellite-navigation system that is inexpensive.
Briefly, a navigation-satellite receiver embodiment of the present invention comprises means for initialization that gets a head start by knowing time to within a few seconds and position to within 150 kilometers. A two-dimensional grid of points is setup with constant altitude that represents solution starting points within the 150 kilometer area. Fractional pseudoranges from each satellite in a constellation are inspected for a best initial fit with the points in the grid. A variety of time bias adjustments within the time bounds are also tried against the points to find a best fitting point. That point then is used to find the final solution and to produce the first fix from cold start.
An advantage of the present invention is that a system and method are provided that produce faster initialization times in navigation satellite receivers.
Another advantage of the present invention is that a system and method are provided for making simple and inexpensive navigation satellite receivers.
These and other objects and advantages of the present invention will no doubt become obvious to those of ordinary skill in the art after having read the following detailed description of the preferred embodiments which are illustrated in the various drawing figures.